package com.sicheng.lc.杂题.多路归并技巧之构造有序链表;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 15:16
 */
public class 查找和最小的K对数字 {
    //https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // (i,j) nums1[i]--->nums2[j]
        // 拓展结点  (i+1,j)
        PriorityQueue<int[]> heap = new PriorityQueue<>(
                (a, b) -> nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]);

        int i = 0;
        for (int j = 0; j < nums2.length; j++) {
            heap.offer(new int[]{i, j});
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int m = 0; m < k; m++) {
            if (heap.isEmpty())
                break;
            int[] p = heap.poll();
            ArrayList<Integer> list = new ArrayList<>(2);
            list.add(nums1[p[0]]);
            list.add(nums2[p[1]]);
            res.add(list);
            if (p[0] + 1 < nums1.length) {
                p[0]++;
                heap.offer(p);
            }
        }

        return res;
    }
}
